"""
计数排序
时间复杂度：O(n)
特点：快
缺点：有范围限制  空间消耗大
"""
import random


def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count + 1)]  # 开辟一个新空间
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):
        for i in range(val):
            li.append(ind)


li = list([random.randint(0, 100) for _ in range(100)])
print(li)
count_sort(li)
print(li)
